package src.java.medium;

/**
 * @author 袁敏
 * @className Solution236
 * @date 2024/7/23
 * @description TODO
 */
public class Solution236 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3, new TreeNode(5, new TreeNode(6), new TreeNode(2, new TreeNode(7), new TreeNode(4))), new TreeNode(1, new TreeNode(0), new TreeNode(8)));
        Solution236 solution236 = new Solution236();
        TreeNode treeNode = solution236.lowestCommonAncestor(root, new TreeNode(5), new TreeNode(1));
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == p || root == q || root == null) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 如果left 和 right都不为空，说明此时root就是最近公共节点
        // 如果left为空，right不为空，就返回right，说明目标节点是通过right返回的，反之亦然。
        if (left != null && right != null) return root;
        if (left == null) return right;
        return left;
    }
}
